package org.example.everyday;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/7/9 0009 21:12
 */
public class Lc873 {
    public static void main(String[] args) {
        Lc873 lc873 = new Lc873();
        int[] arr = {1,2,3,4,5,6,7,8};
        int res = lc873.lenLongestFibSubseq(arr);
        System.out.println(res);

    }


    public int lenLongestFibSubseq(int[] arr) {
        Map<Integer,Integer> indices = new HashMap<Integer,Integer>();
        int n = arr.length;
        for(int i = 0; i < n; i++){
            indices.put(arr[i],i);
        }
        int[][] dp = new int[n][n];
        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = i - 1; j >=0 && arr[j] * 2 > arr[i]; j--){
                int k = indices.getOrDefault(arr[i] - arr[j], -1);
                if(k >= 0){
                    dp[j][i] = Math.max(dp[k][j] + 1 , 3);
                }
                ans = Math.max(ans, dp[j][i]);


            }
        }
        return ans;
    }
}
